- Title
- Graph layout problems parameterized by vertex cover
- Creator
- Fellows, Michael R.; Lokshtanov, Daniel; Misra, Neeldhara; Rosamond, Frances A.; Saurabh, Saket
- Relation
- 19th International Symposium on Algorithms and Computation (ISAAC 2008). Algorithms and Computation: 19th International Symposium, ISAAC 2008 (Gold Coast, Qld 15-17 December, 2008) p. 294-305
- Publisher Link
- http://dx.doi.org/10.1007/978-3-540-92182-0_28
- Publisher
- Springer
- Resource Type
- conference paper
- Date
- 2008
- Description
- In the framework of parameterized complexity, one of the most commonly used structural parameters is the treewidth of the input graph. The reason for this is that most natural graph problems turn out to be fixed parameter tractable when parameterized by treewidth. However, Graph Layout problems are a notable exception. In particular, no fixed parameter tractable algorithms are known for the Cutwidth, Bandwidth, Imbalance and Distortion problems parameterized by treewidth. In fact, Bandwidth remains NP-complete even restricted to trees. A possible way to attack graph layout problems is to consider structural parameterizations that are stronger than treewidth. In this paper we study graph layout problems parameterized by the size of the minimum vertex cover of the input graph. We show that all the mentioned problems are fixed parameter tractable. Our basic ingredient is a classical algorithm for Integer Linear Programming when parameterized by dimension, designed by Lenstra and later improved by Kannan. We hope that our results will serve to re-emphasize the importance and utility of this algorithm.
- Subject
- parameterized complexity; treewidth; integer linear programming; graph layout problems
- Identifier
- uon:6092
- Identifier
- http://hdl.handle.net/1959.13/802442
- Identifier
- ISBN:9783540921813
- Reviewed
- Hits: 1788
- Visitors: 1838
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|